class Solution {
public:
    int countPrimes(int n) {
        if(n < 2) return 0;
        vector<bool> memo(n, 0);//memo[i] == 0 means i+1 is prime, vice versa
        memo[0] = memo[1] = 1;
        for(int i = 2; i * i <= n; i++)
        {
            if(memo[i]) continue;
            int j = i + i;
            while(j < n)
            {
                // cout<<j<<endl;
                memo[j] = 1;
                j += i;
            }
        }
        int res = n;
        for(int i : memo) res -= i;
        return res;
    }
};
